package com.njupt.Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/6/28 14:06
 * @Description: 56. 合并区间
 * @Version: 1.0
 */


public class MergeInterval_56 {


    public int[][] merge(int[][] intervals) {

        if(intervals.length == 1){
            return intervals;
        }

        int[][] array = Arrays.stream(intervals).sorted((v1, v2) -> {
            return v1[0] - v2[0];
        }).toArray(int[][]::new);

        ArrayList<int[]> result = new ArrayList<>();
        int index = -1;
        int i = 0;
        for(i = 0; i< intervals.length-1;i++){
            if(array[i][1] >= array[i + 1][0] && array[i][1] <= array[i + 1][1]){
                result.add(new int[]{array[i][0],array[i + 1][1]});
                index++;
                i++;
            } else if (array[i][1] >= array[i + 1][0] && array[i][1] > array[i + 1][1]) {
                result.add(array[i]);
                index++;
                i++;
            } else {
                result.add(array[i]);
                index++;
            }
        }
        if(i == intervals.length -1){
            if(result.get(index)[1] >= array[i][0] && result.get(index)[1] <= array[i][1]){
                result.get(index)[1] = array[i][1];
            } else if (result.get(index)[1] >= array[i][0] && result.get(index)[1] > array[i][1]) {
                result.get(index)[1] = result.get(index)[1];
            } else {
                result.add(array[i]);
            }
        }
        return result.stream().toArray(int[][]::new);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
//        int[][] intervals = {{1,4},{2,3}};
        MergeInterval_56 test = new MergeInterval_56();
        int[][] merge = test.merge(intervals);

        for(int i = 0;i < merge.length; i++){
            for(int j = 0 ;j < merge[i].length; j++){
                System.out.print(merge[i][j] + " ");
            }
            System.out.println();
        }
    }
}
